package leetcode_1000;

//给定一个数组 问有多少连续子数组的和是K的整数倍
public class SubarraySumsDivisibleByK_974_ {
	//计算连续数组和的与K的余数 相同的余数相减就会得到结果
	public int subarraysDivByK(int[] A, int K) {
		int sum[] = new int[A.length+1];
		for(int i=0;i<A.length;++i)
			sum[i+1] = sum[i]+A[i];
		int count[] = new int[K];//计算每个值出现的次数
		for(int i:sum)
			++count[(i % K + K)%K];
		int res = 0;
		for(int i:count)
			res += i*(i-1)/2;
		return res;
    }
}
